package org.hmh.base;

import java.util.Arrays;

/**
 * Created this one by HMH on 2018/1/20.
 */
public class HeapSort {

    private static void hSort(int arr[]) {
        int len = arr.length - 1;
        build(arr, len);
        while (len > 1) {
            swap(arr, 1, len);
            shift(arr, 1, --len);
        }
    }

    private static void build(int[] arr, int len) {
        for (int i = len / 2; i >= 1; i--) {
            shift(arr, i, len);
        }
    }

    private static void shift(int[] arr, int i, int len) {
        while (2 * i <= len) {
            int j = 2 * i;
            if (j < len && arr[j] < arr[j + 1]) {
                j++;
            }
            if (arr[i] >= arr[j]) {
                break;
            }
            swap(arr, i, j);
            i = j;
        }
    }

    private static void swap(int[] arr, int l, int h) {
        int temp = arr[l];
        arr[l] = arr[h];
        arr[h] = temp;
    }

    public static void main(String[] args){
        int arr[] = {1,5,6,7,3,2,4,5,3,123,12,3,235,6,5};
        hSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
